1. Field of the Invention
The present invention relates generally to a data processing system and method employing an improved form of hashing to provide a dictionary, i.e., a data structure that allows a sequence of on-line insertions, deletions and lookup operations for keys drawn from a universe U. More particularly, it relates to such a data processing system and method that is particularly advantageous when the system hardware allows parallel memory reads in different memory banks. Most especially, it relates to such a data processing system and method utilized in interconnected local area networks to direct information between addresses on the networks.
2. Description of the Prior Art
A variety of techniques for looking up network addresses in local area networks and interconnected local area networks are known in the art. Network address lookup imposes demanding requirements for large scale interconnected networks. For example, consider an Ethernet bridge, linking 20 Ethernets with a total of 50,000 stations. When an information packet comes to the bridge, the bridge hardware must read its destination and determine on which wire to send out the packet. It is desirable that packets arriving at the bridge suffer no delay. Since it typically takes 5 .mu.s to receive a packet, the packets need to be re-routed at a rate of approximately 5 .mu.s. However, we can assume that many (up to 20) packets come to the bridge simultaneously. Therefore, it is necessary to build hardware and algorithms that are able to answer 20 parallel searches among 50,000 entries in less than 5 .mu.s.